#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007
class Solution {
public:
    std::array<int, 3> arr={1,7,30};
    std::array<int, 366> arr2;
    int mincostTickets1(std::vector<int>& days, std::vector<int>& costs) {
        arr2.fill(std::numeric_limits<int>::max());
       return  f(0, days, costs);
    }
    //当在第
    int f(int i,std::vector<int>& days, std::vector<int>& costs)
    {
      
        int n = days.size();
        if (i>=n) return 0;
        if (arr2[i]!=std::numeric_limits<int>::max()) return arr2[i];
        int ans = std::numeric_limits<int>::max();
        for (int j = 0;j<3;j++)
        {
            int k = i+1;
            while (k<n&&days[i] + arr[j] > days[k])
            {
                k++;
            }
            ans=std::min(ans,costs[j]+f(k,days,costs));
        }
        arr2[i]=ans;
        return ans;
    }

    int mincostTickets2(std::vector<int>& days, std::vector<int>& costs) {
        arr2.fill(std::numeric_limits<int>::max());
        int n = days.size();
        arr2[n] = 0;
        for (int i=n-1;i>=0;i--)
        {
            
         for (int j=0;j<3;j++)
         {int k=i+1;
             while (k<n&&days[i] + arr[j] > days[k])
             {
                 k++;
             }
             arr2[i]=std::min(arr2[i],costs[j]+arr2[k]);
         }
        }
        return  arr2[0];
    }
    
};
